package com.haidechizi.backup.sort;

import java.util.Arrays;


/**
 * 希尔排序
 * <p>
 * 按照补偿排序的一种插入排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void shellSort(int[] arr) {

        // 遍历所有的步长
        for (int d = arr.length / 2; d > 0; d /= 2) {
            // 遍历所有的元素
            for (int i = d; i < arr.length; i++) {

                // 记录当前组中需要排序的元素
                int temp = arr[i];
                int j;
                // 遍历当前组中的元素
                for (j = i - d; j >= 0 && arr[j] > temp; j -= d) {
                    // 妈祖条件，将数据移到j+d的位置上去
                    arr[j + d] = arr[j];
                }
                // 将要排序的数据放入数组数组中
                arr[j + d] = temp;
            }
        }

    }

    //
    public static void shellSort2(int[] arr) {
        // 循环所有步长
        for (int d = arr.length / 2; d > 0; d /= 2) {
            // 遍历所有数据
            for (int i = d; i < arr.length; i++) {
                // 遍历当前组中得所有数据
                for (int j = i - d; j >= 0; j = j - d) {
                    if (arr[j] > arr[j + d]) {
                        int temp = arr[j];
                        arr[j] = arr[j + d];
                        arr[j + d] = temp;
                    }
                }
            }

        }
    }
}
